package com.example.demo.interview;

import java.sql.SQLOutput;
import java.util.Arrays;

/**
 * @Author：wangsheng
 * @Description：二分查找,jdk已经实现Arrays.binarySearch
 * @Date：2021/11/26 18:37
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] array = {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50};
        int target = 48;
        int idx = binarySearch(array, target);
        System.out.println(idx);
        System.out.println(Arrays.binarySearch(array,target));
    }

    public static int binarySearch(int[] a, int t) {
        if (a.length > 0) {
            int left = 0, right = a.length - 1, mid;
            while (left <= right) {
                // 注意正数内存溢出问题 int最大值+int/2 肯定内存溢出
                mid = (left + right) >>> 1;
                if (a[mid] == t) {
                    return mid;
                }
                if (a[mid] < t) {
                    left = mid + 1;
                }
                if (a[mid] > t) {
                    right = mid - 1;
                }

            }
        }
        return -1;
    }
}
